{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Zigzag Conversion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: convert"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #N 字形变换"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>将一个给定字符串 <code>s</code> 根据给定的行数 <code>numRows</code> ，以从上往下、从左到右进行 Z 字形排列。</p>\n",
    "\n",
    "<p>比如输入字符串为 <code>\"PAYPALISHIRING\"</code> 行数为 <code>3</code> 时，排列如下：</p>\n",
    "\n",
    "<pre>\n",
    "P   A   H   N\n",
    "A P L S I I G\n",
    "Y   I   R</pre>\n",
    "\n",
    "<p>之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：<code>\"PAHNAPLSIIGYIR\"</code>。</p>\n",
    "\n",
    "<p>请你实现这个将字符串进行指定行数变换的函数：</p>\n",
    "\n",
    "<pre>\n",
    "string convert(string s, int numRows);</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"PAYPALISHIRING\", numRows = 3\n",
    "<strong>输出：</strong>\"PAHNAPLSIIGYIR\"\n",
    "</pre>\n",
    "<strong>示例 2：</strong>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"PAYPALISHIRING\", numRows = 4\n",
    "<strong>输出：</strong>\"PINALSIGYAHRPI\"\n",
    "<strong>解释：</strong>\n",
    "P     I    N\n",
    "A   L S  I G\n",
    "Y A   H R\n",
    "P     I\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"A\", numRows = 1\n",
    "<strong>输出：</strong>\"A\"\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= s.length <= 1000</code></li>\n",
    "\t<li><code>s</code> 由英文字母（小写和大写）、<code>','</code> 和 <code>'.'</code> 组成</li>\n",
    "\t<li><code>1 <= numRows <= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [zigzag-conversion](https://leetcode.cn/problems/zigzag-conversion/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [zigzag-conversion](https://leetcode.cn/problems/zigzag-conversion/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"PAYPALISHIRING\"\\n3', '\"PAYPALISHIRING\"\\n4', '\"A\"\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countDigits(self, num: int) -> int:\r\n",
    "        count = 0\r\n",
    "        convert = str(num)\r\n",
    "        for char in convert:\r\n",
    "            if num % int(char) == 0:\r\n",
    "                count += 1\r\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dayOfYear(self, date):\n",
    "        \"\"\"\n",
    "\n",
    "        \"\"\"\n",
    "        #处理异常情况\n",
    "        if date == None or len(date) == 0:\n",
    "            return -1\n",
    "\n",
    "        #处理字符串, 得到年月日\n",
    "        year_str, month_str, day_str = date[:4], date[5: 7], date[8:]\n",
    "        year = self.convertStr2Int(year_str)\n",
    "        month = self.convertStr2Int(month_str)\n",
    "        day = self.convertStr2Int(day_str)\n",
    "\n",
    "        #判断该年是否是闰年\n",
    "        flag = self.isLeapYear(year)\n",
    "        month_days = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]\n",
    "        if flag:\n",
    "            month_days[2] += 1\n",
    "\n",
    "        #计算月份的前缀数组\n",
    "        pre_month_days = [0 for _ in range(13)]\n",
    "        for i in range(2, 13):\n",
    "            pre_month_days[i] = pre_month_days[i - 1] + month_days[i - 1]\n",
    "\n",
    "        #计算最终第几天\n",
    "        return pre_month_days[month] + day \n",
    "\n",
    "    def isLeapYear(self, year):\n",
    "        \"\"\"\n",
    "        判断概念是否是闰年\n",
    "        Args:\n",
    "            year (int):\n",
    "        \n",
    "        \"\"\"\n",
    "        #能被400整除 or (能被4整除但不能被100整除)\n",
    "        if (year % 400 == 0) or (year % 4 == 0 and year % 100 != 0):\n",
    "            return True \n",
    "        else:\n",
    "            return False \n",
    "        \n",
    "    def convertStr2Int(self, s):\n",
    "        \"\"\"\n",
    "        将字符串形式的数字转化为数字\n",
    "        Args:\n",
    "            s(str):\n",
    "        returns (int): \n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = 10 * ans + (ord(s[i]) - ord('0'))\n",
    "        \n",
    "        return ans \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class SQL:\n",
    "\n",
    "    def __init__(self, names: List[str], columns: List[int]):\n",
    "        # Dictionary to hold tables. Each table has a list of rows, and each row is a list of cell values\n",
    "        self.tables = {}\n",
    "        \n",
    "        # Dictionary to hold the next available rowId for each table\n",
    "        self.nextRowId = {}\n",
    "        \n",
    "        for name, column in zip(names, columns):\n",
    "            self.tables[name] = {}\n",
    "            self.nextRowId[name] = 1\n",
    "\n",
    "    def insertRow(self, name: str, row: List[str]) -> None:\n",
    "        table = self.tables[name]\n",
    "        table[self.nextRowId[name]] = row\n",
    "        self.nextRowId[name] += 1\n",
    "\n",
    "    def deleteRow(self, name: str, rowId: int) -> None:\n",
    "        table = self.tables[name]\n",
    "        if rowId in table:\n",
    "            del table[rowId]\n",
    "\n",
    "    def selectCell(self, name: str, rowId: int, columnId: int) -> str:\n",
    "        table = self.tables[name]\n",
    "        if rowId in table and 0 <= columnId-1 < len(table[rowId]):\n",
    "            return table[rowId][columnId-1]  # columnId-1 because we're converting from 1-indexed to 0-indexed\n",
    "        else:\n",
    "            return \"\"  # Or raise an error if needed\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def haveConflict(self, event1: List[str], event2: List[str]) -> bool:\n",
    "        def convert(t):\n",
    "            h, m = map(int, t.split(':'))\n",
    "            return h * 60 + m\n",
    "        event1 = [convert(t) for t in event1]\n",
    "        event2 = [convert(t) for t in event2]\n",
    "        if event1[1] < event2[0] or event1[0] > event2[1]:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush, heapreplace\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def convertArray(self, nums: List[int]) -> int:\n",
    "        def cao(y):\n",
    "            h = []\n",
    "            cost = 0\n",
    "            for v in y:\n",
    "                if h and v < -h[0]:\n",
    "                    cost += -v - h[0]\n",
    "                    heapreplace(h, -v)\n",
    "                heappush(h, -v)\n",
    "            return cost\n",
    "\n",
    "        t = cao(nums)\n",
    "        x = nums[::-1]\n",
    "        x = cao(x)\n",
    "        return min(t, x)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertArray(self, nums: List[int]) -> int:\n",
    "        \n",
    "        def cao(y):\n",
    "            h=[]\n",
    "            cost=0\n",
    "            for v in y:\n",
    "                if h  and v< -h[0]:\n",
    "                    cost += -v -h[0] \n",
    "                    heapreplace(h,-v)\n",
    "                heappush(h,-v)\n",
    "            return cost\n",
    "                    \n",
    "        t=cao(nums)\n",
    "        x=nums[::-1]\n",
    "        x=cao(x)\n",
    "        return t if t<x else x\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertArray(self, nums: List[int]) -> int:\n",
    "\n",
    "        def cao(y):\n",
    "            h=[]\n",
    "            cost=0\n",
    "            for v in y:\n",
    "                if h  and v< -h[0]:\n",
    "                    cost += -v -h[0] \n",
    "                    heapreplace(h,-v)\n",
    "                heappush(h,-v)\n",
    "            return cost\n",
    "                    \n",
    "        t=cao(nums)\n",
    "        x=nums[::-1]\n",
    "        x=cao(x)\n",
    "        return t if t<x else x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ceil = 1001\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def convertArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        increase = [0]*ceil\n",
    "        for num in nums:\n",
    "            increase[0] += abs(num)\n",
    "            for j in range(1, ceil):\n",
    "                increase[j] = min(increase[j-1], increase[j]+abs(num-j))\n",
    "\n",
    "        decrease = [0]*ceil\n",
    "        for i in range(n-1, -1, -1):\n",
    "            num = nums[i]\n",
    "            decrease[0] += abs(num)\n",
    "            for j in range(1, ceil):\n",
    "                decrease[j] = min(decrease[j-1], decrease[j]+abs(num-j))\n",
    "        return min(decrease[-1], increase[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertArray(self, nums: List[int]) -> int:\n",
    "        def helper(nums: List[int]) -> int:\n",
    "            \"\"\"变为不减数组的最小操作次数\"\"\"\n",
    "            res, pq = 0, []  # 大根堆\n",
    "            for num in nums:\n",
    "                if not pq:\n",
    "                    heappush(pq, -num)\n",
    "                else:\n",
    "                    preMax = -pq[0]\n",
    "                    if preMax > num:\n",
    "                        res += preMax - num\n",
    "                        heappushpop(pq, -num)\n",
    "                    heappush(pq, -num)\n",
    "            return res\n",
    "\n",
    "        return min(helper(nums), helper(nums[::-1]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def convertArray(self, a: List[int]) -> int:\n",
    "        def f(x):\n",
    "            a = x \n",
    "            ans = 0\n",
    "            b = SortedList([a[0]])\n",
    "            for j in a[1:]:\n",
    "                if j<b[-1]:\n",
    "                    t = b.pop() \n",
    "                    ans += (t - j)\n",
    "                    b.add(j)\n",
    "                b.add(j)\n",
    "            return ans \n",
    "        return min(f(a), f(a[::-1]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertArray(self, nums: List[int]) -> int:\n",
    "        def cal(A):\n",
    "            pq = []\n",
    "            res = 0\n",
    "            for a in A:\n",
    "                heappush(pq,-a)\n",
    "                if -pq[0]>a:\n",
    "                    res += -pq[0]-a\n",
    "                    heappushpop(pq,-a)\n",
    "            return res\n",
    "        return min(cal(nums),cal(nums[::-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertArray(self, nums: List[int]) -> int:\n",
    "        def helper(nums: List[int]) -> int:\n",
    "            \"\"\"变为不减数组的最小操作次数\"\"\"\n",
    "            res, pq = 0, []  # 大根堆\n",
    "            for num in nums:\n",
    "                if not pq:\n",
    "                    heappush(pq, -num)\n",
    "                else:\n",
    "                    preMax = -pq[0]\n",
    "                    if preMax > num:\n",
    "                        res += preMax - num\n",
    "                        heappushpop(pq, -num)\n",
    "                    heappush(pq, -num)\n",
    "            return res\n",
    "\n",
    "        return min(helper(nums), helper(nums[::-1]))\n",
    "        \n",
    "\n",
    "    def convertArray2(self, nums: List[int]) -> int:\n",
    "        def helper(nums: List[int]) -> int:\n",
    "            \"\"\"变为不减数组的最小操作次数\"\"\"\n",
    "            n, max_ = len(nums), max(nums)\n",
    "\n",
    "            dp = [[int(1e20)] * (max_ + 1) for _ in range(n)]  # dp[i][num] 表示 前i个元素最num结尾的最小的代价是多少\n",
    "            for j in range((max_ + 1)):\n",
    "                dp[0][j] = abs(nums[0] - j)\n",
    "            for i in range(1, n):\n",
    "                preMin = int(1e20)\n",
    "                for j in range((max_ + 1)):\n",
    "                    preMin = min(preMin, dp[i - 1][j])\n",
    "                    dp[i][j] = preMin + abs(nums[i] - j)\n",
    "\n",
    "            return min(dp[-1])\n",
    "\n",
    "        return min(helper(nums), helper(nums[::-1]))\n",
    "        \n",
    "    def convertArray3(self, nums: List[int]) -> int:\n",
    "        def helper(nums: List[int]) -> int:\n",
    "            \"\"\"变为不减数组的最小操作次数\n",
    "\n",
    "            取得最小的操作次数时，数组末尾元素必须等于原数组中的某个元素\n",
    "            dp[i][num]表示前i个元素以num结尾的最小的代价是多少 时间复杂度 O(n*max(num[i]))\n",
    "            \"\"\"\n",
    "            n = len(nums)\n",
    "            allNums = sorted(set(nums))\n",
    "            m = len(allNums)\n",
    "\n",
    "            dp = [[int(1e20)] * m for _ in range(n)]\n",
    "            for j in range((m)):\n",
    "                dp[0][j] = abs(nums[0] - allNums[j])\n",
    "            for i in range(1, n):\n",
    "                preMin = int(1e20)\n",
    "                for j in range(m):\n",
    "                    preMin = min(preMin, dp[i - 1][j])\n",
    "                    dp[i][j] = preMin + abs(nums[i] - allNums[j])\n",
    "\n",
    "            return min(dp[-1])\n",
    "\n",
    "        return min(helper(nums), helper(nums[::-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "import sys\n",
    "from sortedcontainers import SortedList\n",
    "sys.setrecursionlimit(999999)\n",
    "class Solution:\n",
    "    def convertArray(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        def get_ans(list1):\n",
    "            ans = 0\n",
    "            sd1 = SortedList()\n",
    "            for i in list1:\n",
    "                if len(sd1) == 0:\n",
    "                    sd1.add(i)\n",
    "                else:\n",
    "                    if sd1[-1] > i:\n",
    "                        xx = sd1.pop()\n",
    "                        sd1.add(i)\n",
    "                        ans += xx - i\n",
    "                    sd1.add(i)\n",
    "            return ans\n",
    "\n",
    "        ans1 = get_ans(nums)\n",
    "        ans2 = get_ans(nums[::-1])\n",
    "        return min(ans1, ans2)\n",
    "\n",
    "a = Solution()\n",
    "print(a.convertArray([3,2,4,5,0]))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertArray(self, nums: List[int]) -> int:\n",
    "        def helper(nums: List[int]) -> int:\n",
    "            \"\"\"变为不减数组的最小操作次数\n",
    "\n",
    "            取得最小的操作次数时，数组末尾元素必须等于原数组中的某个元素\n",
    "            \"\"\"\n",
    "            n = len(nums)\n",
    "            allNums = sorted(set(nums))\n",
    "            m = len(allNums)\n",
    "\n",
    "            dp = [[int(1e20)] * m for _ in range(n)]\n",
    "            for j in range((m)):\n",
    "                dp[0][j] = abs(nums[0] - allNums[j])\n",
    "            for i in range(1, n):\n",
    "                preMin = int(1e20)\n",
    "                for j in range(m):\n",
    "                    preMin = min(preMin, dp[i - 1][j])\n",
    "                    dp[i][j] = preMin + abs(nums[i] - allNums[j])\n",
    "\n",
    "            return min(dp[-1])\n",
    "\n",
    "        return min(helper(nums), helper(nums[::-1]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertArray(self, nums: List[int]) -> int:\n",
    "        def helper(nums: List[int]) -> int:\n",
    "            \"\"\"变为不减数组的最小操作次数\n",
    "\n",
    "            取得最小的操作次数时，数组末尾元素必须等于原数组中的某个元素\n",
    "            \"\"\"\n",
    "            n = len(nums)\n",
    "            allNums = sorted(set(nums))\n",
    "            m = len(allNums)\n",
    "\n",
    "            dp = [[int(1e20)] * m for _ in range(n)]\n",
    "            for j in range((m)):\n",
    "                dp[0][j] = abs(nums[0] - allNums[j])\n",
    "            for i in range(1, n):\n",
    "                preMin = int(1e20)\n",
    "                for j in range(m):\n",
    "                    preMin = min(preMin, dp[i - 1][j])\n",
    "                    dp[i][j] = preMin + abs(nums[i] - allNums[j])\n",
    "\n",
    "            return min(dp[-1])\n",
    "\n",
    "        return min(helper(nums), helper(nums[::-1]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertArray(self, nums: List[int]) -> int:\n",
    "        def helper(nums: List[int]) -> int:\n",
    "            \"\"\"变为不减数组的最小操作次数\"\"\"\n",
    "            n, max_ = len(nums), max(nums)\n",
    "\n",
    "            dp = [[int(1e20)] * (max_ + 1) for _ in range(n)]  # dp[i][num] 表示 前i个元素最num结尾的最小的代价是多少\n",
    "            for j in range((max_ + 1)):\n",
    "                dp[0][j] = abs(nums[0] - j)\n",
    "            for i in range(1, n):\n",
    "                preMin = int(1e20)\n",
    "                for j in range((max_ + 1)):\n",
    "                    preMin = min(preMin, dp[i - 1][j])\n",
    "                    dp[i][j] = preMin + abs(nums[i] - j)\n",
    "\n",
    "            return min(dp[-1])\n",
    "\n",
    "        return min(helper(nums), helper(nums[::-1]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "\n",
    "        num_map = {}\n",
    "\n",
    "        def convert(c_list):\n",
    "            num = 0\n",
    "            x = 1\n",
    "            for i in range(8):\n",
    "                num += x * c_list[i]\n",
    "                x = x << 1\n",
    "            num_map[num] = c_list\n",
    "            return num\n",
    "\n",
    "        num_list = []\n",
    "        num_set = set({})\n",
    "        now_num = convert(cells)\n",
    "        num_list.append(now_num)\n",
    "        num_set.add(now_num)\n",
    "        for _ in range(64):\n",
    "            tmp_list = [0] * 8\n",
    "            for j in range(1, 7):\n",
    "                tmp_list[j] = 1 - cells[j-1] ^ cells[j+1]\n",
    "            cells = tmp_list\n",
    "            now_num = convert(cells)\n",
    "            if now_num in num_set:\n",
    "                break\n",
    "\n",
    "            num_list.append(now_num)\n",
    "            num_set.add(now_num)\n",
    "        now_num = convert(cells)\n",
    "        if n < len(num_list):\n",
    "            return num_map[num_list[n]]\n",
    "        now_num_index = num_list.index(now_num)\n",
    "        left_num_list = num_list[now_num_index:]\n",
    "        left = (n - len(num_list)) % len(left_num_list)\n",
    "        r_num = left_num_list[left]\n",
    "        return num_map[r_num]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:\n",
    "        seen = set()\n",
    "        og = cells\n",
    "        def toDigit(cells):\n",
    "            return int('0b' + ''.join(map(str, cells)), 2)\n",
    "\n",
    "        def toCell(num):\n",
    "            res = [0] * 8\n",
    "\n",
    "            for i in range(8):\n",
    "                if num & (1 << i):\n",
    "                    res[8 - i - 1] = 1\n",
    "\n",
    "            return res\n",
    "\n",
    "\n",
    "        def convert(cells):\n",
    "            res = [0] * 8\n",
    "\n",
    "            for i in range(1, 7):\n",
    "                if cells[i - 1] == cells[i + 1]:\n",
    "                    res[i] = 1\n",
    "            return res\n",
    "\n",
    "        ll = []\n",
    "        while True:\n",
    "            val = toDigit(cells)\n",
    "            if val in seen:\n",
    "                break\n",
    "            else:\n",
    "                seen.add(val)\n",
    "                cells = convert(cells)\n",
    "                ll.append(val)\n",
    "\n",
    "        for i in range(len(ll)):\n",
    "            if ll[i] == val:\n",
    "                break\n",
    "        \n",
    "        period = len(ll) - 1 - i + 1\n",
    "\n",
    "        if n < i:\n",
    "            return toCell(ll[n])\n",
    "        else:\n",
    "            return toCell(ll[i + (n - i) % period])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s, numRows):\n",
    "        if numRows == 1 or numRows>len(s):  # 特例\n",
    "            return s \n",
    "\n",
    "        zigzag = [\"\" for i in range(numRows)]  # 创建行字符串list\n",
    "        row, step = 0, 1  \n",
    "        for char in s:\n",
    "            zigzag[row] += char\n",
    "            \n",
    "            if  row == numRows-1:\n",
    "                step = -1\n",
    "            elif row == 0:\n",
    "                step = 1\n",
    "            \n",
    "            row += step\n",
    "        \n",
    "        return \"\".join(zigzag)\n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s, numRows):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type numRows: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if numRows == 1:\n",
    "            return s\n",
    "        arr = [''] * numRows\n",
    "        r = numRows * 2 - 2\n",
    "        for i, c in enumerate(s):\n",
    "            if i % r < numRows:\n",
    "                arr[i % r] += c\n",
    "            else:\n",
    "                arr[r - i % r] += c\n",
    "        return ''.join(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s, numRows):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type numRows: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        res=\"\"\n",
    "        for i in range(0,numRows):\n",
    "            j=i\n",
    "            cycle1=2*numRows-2*i-2\n",
    "            cycle2=2*i\n",
    "            \n",
    "            if cycle1==0 and cycle2==0:return s\n",
    "            \n",
    "            while j<len(s) :\n",
    "                if cycle1!=0:\n",
    "                    res=res+s[j]\n",
    "                    j=j+cycle1\n",
    "                if j>=len(s):\n",
    "                    break\n",
    "                if cycle2!=0:\n",
    "                    res=res+s[j]\n",
    "                    j=j+cycle2\n",
    "                \n",
    "                \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:     \n",
    "        if numRows == 1:\n",
    "            return s\n",
    "        result_list = ['' for i in range(numRows)]\n",
    "        num_list = numRows*2-2\n",
    "        for i in range(len(s)):\n",
    "            yu = i%num_list\n",
    "            if yu < numRows:\n",
    "                result_list[yu] = result_list[yu]+s[i]\n",
    "                \n",
    "            else:\n",
    "                result_list[num_list - yu] = result_list[num_list - yu] + s[i]\n",
    "             \n",
    "        return ''.join(result_list)\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s, numRows):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type numRows: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if numRows == 1:\n",
    "            return s\n",
    "        new_lst = [[] for _ in range(numRows)]\n",
    "        divide = 2 * (numRows - 1)\n",
    "        dd = {k % divide: k for k in range(1, numRows + 1)}\n",
    "        dd.update({k % divide: divide + 2 - k for k in range(numRows + 1, divide + 1)})\n",
    "        for i, x in enumerate(s):\n",
    "            new_lst[dd[(i + 1) % divide] - 1].append(x)\n",
    "        return \"\".join([x for ll in new_lst for x in ll])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: 'str', numRows: 'int') -> 'str':\n",
    "        str_list = []\n",
    "        cur_row = 0\n",
    "        growth = 1\n",
    "        if numRows == 1:\n",
    "            return s\n",
    "        for num in range(min(numRows, len(s))):\n",
    "            str_list.append('')\n",
    "        for char in s:\n",
    "            print(cur_row)\n",
    "            str_list[cur_row] += char\n",
    "            if cur_row % numRows == (numRows - 1):\n",
    "                growth = -1\n",
    "            if cur_row % numRows == 0:\n",
    "                growth = 1\n",
    "            cur_row += growth\n",
    "\n",
    "        res = ''.join(str_list)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s, numRows):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type numRows: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        #可以看做是半z字形重复出现的序列，半z字形的长度为2*numRows-2，将整个字符串的长度对2*numRows-2取余\n",
    "        if numRows == 1:\n",
    "            return s\n",
    "        string = \"\"\n",
    "        length = len(s)\n",
    "        length0 = 2 * numRows - 2\n",
    "        i = 0\n",
    "        print(\"length: \", length)\n",
    "        print(\"length0: \", length0)\n",
    "        while(i < numRows):\n",
    "            print(\"i: \", i)\n",
    "            j = 0\n",
    "            while(i + j < length):\n",
    "                print(\"j: \",j)\n",
    "                string += s[j + i]\n",
    "                if i != 0 and i != numRows - 1 and j + length0 - i < length:\n",
    "                    string += s[j + length0 - i]\n",
    "                j += length0\n",
    "            i += 1\n",
    "        return string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: 'str', numRows: 'int') -> 'str':\n",
    "        box = ''\n",
    "        l   = len(s)\n",
    "        \n",
    "        if numRows == 1:\n",
    "            return s\n",
    "    \n",
    "        for i in range(numRows):\n",
    "            j = i\n",
    "            while j < l:\n",
    "                box = box + s[j]\n",
    "                if i!=0 and i!=numRows-1:\n",
    "                    m = j + (numRows-i)*2-2\n",
    "                    if m < l:\n",
    "                        box = box + s[m]\n",
    "                        print(s[m])\n",
    "                j = j + numRows*2-2\n",
    "        return box\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s, numRows):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type numRows: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        if n < 2 or numRows == 1:\n",
    "            return s\n",
    "        sNew = '' # 怎么样建一个大小相同的空数组？\n",
    "        for l in range(1, numRows+1):\n",
    "            i = k1 = k2 = 0\n",
    "            print(l)\n",
    "            while k1 <= n:\n",
    "                print(k1, k2)\n",
    "                k1 = l - 1 + (2*numRows - 2)*i\n",
    "                k2 = k1 - 2 * (l - 1)\n",
    "                if 0 <= k2 < n and 1 < l < numRows:\n",
    "                    sNew = sNew + s[k2]\n",
    "                if 0 <= k1 < n:\n",
    "                    sNew = sNew + s[k1]\n",
    "                i += 1\n",
    "               \n",
    "        return sNew"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s, numRows):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type numRows: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if numRows == 1 or numRows >= len(s):\n",
    "            return s\n",
    "        \n",
    "        step,index=1,0\n",
    "        temp=[\"\"]*numRows\n",
    "        for x in s:\n",
    "            print(x)\n",
    "            temp[index]+=x\n",
    "            if index==0:\n",
    "                step=1\n",
    "            if index==numRows-1:\n",
    "                step=-1\n",
    "            index+=step\n",
    "        return ''.join(temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        if numRows==1:\n",
    "            return s\n",
    "        lst=[]\n",
    "        st=''\n",
    "        for i in range(numRows):\n",
    "            lst.append([])\n",
    "        j=-1\n",
    "        ofs=True\n",
    "        for i in s:\n",
    "            if j+1<numRows and ofs:\n",
    "                j+=1\n",
    "                lst[j].append(i)\n",
    "            elif j>0:\n",
    "                ofs=False\n",
    "                j-=1\n",
    "                lst[j].append(i)\n",
    "            else:\n",
    "                ofs=True\n",
    "                j+=1\n",
    "                lst[j].append(i)               \n",
    "        for i in lst:\n",
    "            st+=''.join(i)\n",
    "        return st"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        res = ''\n",
    "        n = len(s)\n",
    "        if n == 0:\n",
    "            return res\n",
    "        if numRows <= 1:\n",
    "            return s\n",
    "        \n",
    "        T = 2*(numRows-1)\n",
    "        for j in range(0, n, T):\n",
    "            res += s[j]\n",
    "\n",
    "        for i in range(1, numRows-1):\n",
    "            # idx = sorted(list(range(i, n, T)) + list(range(T-i, n, T)))\n",
    "            for j in range(i, n, T):\n",
    "                res += s[j]\n",
    "                if j+T-2*i < n:\n",
    "                    res += s[j+T-2*i]\n",
    "\n",
    "        for j in range(numRows-1, n, T):\n",
    "            res += s[j]\n",
    "\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        if numRows < 2:\n",
    "            return s\n",
    "            \n",
    "        res = [\"\" for _ in range(numRows)]\n",
    "\n",
    "        i, flag = 0, -1\n",
    "        for c in s:\n",
    "            res[i] += c\n",
    "            if i == 0 or i == numRows - 1: \n",
    "                flag = -flag\n",
    "            i += flag\n",
    "\n",
    "        return \"\".join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        if numRows < 2: return s\n",
    "        res = ['' for _ in range(numRows)]\n",
    "        i ,flag = 0, -1\n",
    "        for c in s:\n",
    "            res[i] += c\n",
    "            if i == 0 or i == numRows-1:\n",
    "                flag *= -1\n",
    "            i += flag\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        if numRows < 2:\n",
    "             return s\n",
    "        res = [\"\" for _ in range(numRows)]\n",
    "        i = 0\n",
    "        flag = -1\n",
    "        for c in s:\n",
    "            res[i] += c\n",
    "            if i == 0 or i == numRows - 1: \n",
    "                flag = -flag\n",
    "            i += flag\n",
    "        return \"\".join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        if len(s) == 0 or numRows == 1:\n",
    "            return s\n",
    "\n",
    "        result = ''\n",
    "\n",
    "        for row in range(numRows):\n",
    "            temp = ''\n",
    "            i = row\n",
    "            space = 2*(numRows-1)\n",
    "            left = space -2*row\n",
    "            while i<len(s):\n",
    "                temp= temp+ s[i]\n",
    "                if row == 0 or row == (numRows - 1):\n",
    "                    i = i + space\n",
    "                else:\n",
    "                    i= i+ left\n",
    "                    left = space-left\n",
    "            result = result + temp\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type numRows: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if(numRows == 1): return s\n",
    "        #产生一个有numrows单元的list，每个list可以在后面添加元素\n",
    "        a = [[]for i in range(numRows)]\n",
    "        r = 0\n",
    "        direct = 1 #行前进的方向是向上还是向下\n",
    "        for c in s:\n",
    "            a[r].append(c)\n",
    "            if r >=numRows-1:\n",
    "                direct = -1\n",
    "            elif r == 0:\n",
    "                direct = 1\n",
    "            r +=direct\n",
    "        answer = \"\"\n",
    "        for row in a:#按行优先打印出来\n",
    "            for col in row:\n",
    "                answer += col\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        d = numRows +numRows-2\n",
    "        s0 = []\n",
    "        s1=\"\"\n",
    "        if numRows==1 or len(s)<=numRows:\n",
    "            return s\n",
    "        (e,p) = divmod(len(s),d)\n",
    "        for i in range(numRows):\n",
    "            if p==0:\n",
    "                for j in range(e):\n",
    "                    if i==0 or i==d/2:\n",
    "                        s0.append(s[i+d*j])\n",
    "                    else:\n",
    "                        s0.append(s[i+d*j])\n",
    "                        s0.append(s[d*(j+1)-i])\n",
    "            else:\n",
    "                for k in range(d-p):\n",
    "                    s+=' '\n",
    "                for j in range(e+1):\n",
    "                    if i==0 or i==d/2:\n",
    "                        s0.append(s[i+d*j])\n",
    "                    else:\n",
    "                        s0.append(s[i+d*j])\n",
    "                        s0.append(s[d*(j+1)-i])\n",
    "                for i in range(s0.count(' ')):\n",
    "                    s0.remove(' ')\n",
    "        for i in s0:\n",
    "            s1+=i\n",
    "        return s1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        length = len(s)\n",
    "        if numRows == 1:\n",
    "            return s\n",
    "        T = 2 * numRows - 2\n",
    "        newseq = ''\n",
    "        for i in range(numRows):\n",
    "            if i == 0 or i == numRows - 1:\n",
    "                index = i\n",
    "                while index < length:\n",
    "                    newseq = newseq + s[index]\n",
    "                    index = index + T\n",
    "            else:\n",
    "                first_index = i\n",
    "                second_index = i + 2 * (numRows - 1 - i)\n",
    "                while first_index < length or second_index < length:\n",
    "\n",
    "                    if first_index < length:\n",
    "                        newseq = newseq + s[first_index]\n",
    "                        first_index = first_index + T\n",
    "\n",
    "                    if second_index < length:\n",
    "                        newseq = newseq + s[second_index]\n",
    "                        second_index = second_index + T\n",
    "        return newseq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        if numRows == 1:\n",
    "            return s\n",
    "        # else:\n",
    "        #     string = ''\n",
    "        #     for i in range(numRows):\n",
    "        #         for j in range(len(s)):\n",
    "        #             if j % (2*numRows-2) == i or j % (2*numRows-2) == 2*numRows-2-i:\n",
    "        #                 string += s[j]\n",
    "        #     return string\n",
    "        res = ['']*numRows\n",
    "        group_idx = 0\n",
    "        ordd = -1\n",
    "        for i in range(len(s)):\n",
    "            res[group_idx] += s[i]\n",
    "            if i % (numRows-1) == 0:\n",
    "                ordd = -ordd\n",
    "            group_idx += ordd\n",
    "        return ''.join(res)\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        if numRows == 1: return s\n",
    "        res = ['']*numRows\n",
    "        l = 2*numRows-2\n",
    "        for i in range(len(s)):\n",
    "            r = i%l\n",
    "            f = r if r < numRows else l-r\n",
    "            res[f] += s[i]\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        s_array = [[] for _ in range(numRows)]\n",
    "        index = [i for i in range(numRows)] + [i for i in range(numRows-2, 0, -1)]\n",
    "        index_len = len(index)\n",
    "        p = 0\n",
    "        for i in range(len(s)):\n",
    "            s_array[index[p]].append(s[i])\n",
    "            p += 1\n",
    "            p = p % (index_len)\n",
    "        s = ''\n",
    "        for i in range(numRows):\n",
    "            s += ''.join(s_array[i])\n",
    "        return s\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        if len(s)<= numRows or numRows==1:\n",
    "            return s \n",
    "        ans = []\n",
    "        for i in range(numRows):\n",
    "            stp1 = 2 * numRows - 2 - 2 * i \n",
    "            stp2 = 2 * (i+1) - 2\n",
    "            if stp1 == 0:\n",
    "                ans.append(s[i::stp2])\n",
    "            elif stp2 == 0:\n",
    "                print(stp1)\n",
    "                ans.append(s[i::stp1])\n",
    "            else:\n",
    "                cur = i\n",
    "                cnt = 0 \n",
    "                while cur<len(s):\n",
    "                    if cnt%2==0:\n",
    "                        ans.append(s[cur])\n",
    "                        cur+=stp1\n",
    "                    else:\n",
    "                        ans.append(s[cur])\n",
    "                        cur+=stp2\n",
    "                    cnt+=1\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        if numRows == 1 or len(s) <= numRows:\n",
    "            return s\n",
    "        \n",
    "        #创建 numRows 个字符串，用于存储每行的字符\n",
    "        row = ['']*numRows\n",
    "        index, step = 0,1\n",
    "        \n",
    "        for char in s:\n",
    "            row[index] += char\n",
    "\n",
    "            #到达Z字形的转折点，改变遍历方向\n",
    "            if index == 0:\n",
    "                step = 1\n",
    "            elif index == numRows - 1:\n",
    "                step = -1\n",
    "\n",
    "            index += step\n",
    "        return ''.join(row)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        if numRows < 2: return s\n",
    "        stringList = [[] for _ in range(numRows)]\n",
    "        Turn = False\n",
    "        Row = 0\n",
    "        for i in range(len(s)):\n",
    "            if not Turn:\n",
    "                stringList[Row].append(s[i])\n",
    "                if i + 1 % numRows + 1 == 0 or Row == numRows - 1:\n",
    "                    Turn = True\n",
    "                    Row -= 2\n",
    "                Row += 1\n",
    "            else:\n",
    "                stringList[Row].append(s[i])\n",
    "                if Row == 0:\n",
    "                    Turn = False\n",
    "                    Row += 2\n",
    "                Row -= 1\n",
    "        OutString = \"\"\n",
    "        for i in range(len(stringList)):\n",
    "            for j in range(len(stringList[i])):\n",
    "                OutString += stringList[i][j]\n",
    "        return OutString\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        \n",
    "        \n",
    "        if numRows==1:\n",
    "            return s\n",
    "        \n",
    "        k=len(s)\n",
    "        \n",
    "        n=numRows\n",
    "\n",
    "        t=(k-2+n)//(2*n-2)\n",
    "        \n",
    "        rows=(t+1)+t*(n-2)\n",
    "        \n",
    "        dp = [[] for row in range(n)]\n",
    "        \n",
    "        top2end=1\n",
    "\n",
    "        \n",
    "        index1=-1\n",
    "        for index,ss in enumerate(s):\n",
    "            \n",
    "            if(top2end==1 ):\n",
    "               index1=index1+1\n",
    "               dp[index1].append(ss)\n",
    "               \n",
    "            else:\n",
    "               index1=index1-1\n",
    "               dp[index1].append(ss)\n",
    "               \n",
    "            if index1==n-1 and top2end:\n",
    "                top2end=0\n",
    "            elif index1==0 and  top2end==0:\n",
    "                top2end=1\n",
    "           \n",
    "        strr=\"\"\n",
    "        \n",
    "        for dd in  dp:\n",
    "            for ddd in dd:\n",
    "                strr=strr+ddd\n",
    "            \n",
    "        return strr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        if numRows == 1:\n",
    "            return s\n",
    "\n",
    "        cnt = 2*numRows-2\n",
    "        a, b = divmod(len(s), cnt)\n",
    "        mats = []\n",
    "        for i in range(a):\n",
    "            mats.append(s[i*cnt:i*cnt+numRows])\n",
    "            for j in range(numRows-2):\n",
    "                mats.append(' '*(numRows-j-2)+s[i*cnt+numRows+j]+' '*(j+1))\n",
    "        \n",
    "        if b > numRows:\n",
    "            mats.append(s[-b:-(b-numRows)])\n",
    "            for j in range(b-numRows):\n",
    "                mats.append(' '*(numRows-j-2)+s[-(b-numRows-j)]+' '*(j+1))\n",
    "        elif b > 0:\n",
    "             mats.append(s[-b:]+' '*(numRows-b))\n",
    "        \n",
    "        ans = [c for x in zip(*mats) for c in x if not c.isspace()]\n",
    "        return ''.join(ans)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        res = ['' for i in range(numRows)]\n",
    "        if numRows == 1:\n",
    "            return s\n",
    "        def trac(s):\n",
    "            s_now = s[:2*numRows-2]\n",
    "            if s_now == '':\n",
    "                return \n",
    "            n = len(s_now)\n",
    "            for i in range(n):\n",
    "                if i < numRows:\n",
    "                    res[i] += s_now[i]\n",
    "                else:\n",
    "                    res[2*numRows-i-2] += s_now[i]\n",
    "            trac(s[2*numRows-2:])\n",
    "        trac(s)\n",
    "        rr = ''\n",
    "        for i in res:\n",
    "            rr += i \n",
    "        return rr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def dfs(self, nowx: int, nowdir: int, pos: int):\n",
    "        print(nowx)\n",
    "        self.ans[nowx].append(self.s[pos]) \n",
    "        if(pos == len(self.s)-1):\n",
    "            return\n",
    "        nexx = nowx + nowdir\n",
    "        if(nexx==self.numRows-1 or nexx==0):\n",
    "            nexdir = -nowdir\n",
    "        else:\n",
    "            nexdir = nowdir \n",
    "        self.dfs(nexx, nexdir, pos+1)\n",
    "\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        if(numRows==1):\n",
    "            return s\n",
    "        self.ans = [ [] for i in range(numRows) ]   \n",
    "        self.numRows = numRows\n",
    "        self.s = s  \n",
    "        self.dfs(0, 1, 0)\n",
    "        ass = []\n",
    "        for i in range(numRows):\n",
    "            ass.append(''.join(self.ans[i]))\n",
    "        return ''.join(ass)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        ans = []\n",
    "        if numRows == 1:\n",
    "            return s\n",
    "\n",
    "        final = ''\n",
    "        if numRows == 2:\n",
    "            for i in range(0,len(s),2):\n",
    "                final += s[i]\n",
    "            for j in range(1,len(s),2):\n",
    "                final += s[j]\n",
    "            return final\n",
    "            \n",
    "        near = 0\n",
    "        stack = []\n",
    "        for i in s:\n",
    "            if near > 0:\n",
    "                temp = ['' for i in range(near)]\n",
    "                temp.append(i)\n",
    "                ans.append(temp)\n",
    "                near -= 1\n",
    "            else:\n",
    "                if len(stack) < numRows:\n",
    "                    stack.append(i)\n",
    "                elif len(stack) == numRows:\n",
    "                    ans.append(stack)\n",
    "                    stack = []\n",
    "                    near = numRows - 3\n",
    "                    temp = ['' for i in range(numRows - 2)]\n",
    "                    temp.append(i)\n",
    "                    ans.append(temp)\n",
    "        if stack != []:\n",
    "            ans.append(stack)\n",
    "\n",
    "        for i in range(numRows):\n",
    "            for j in ans:\n",
    "                try:\n",
    "                    final += j[i]\n",
    "                except:\n",
    "                    pass\n",
    "        return final"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        if numRows == 1:\n",
    "            return s\n",
    "        s1 = []\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            tmp = i % (numRows + numRows - 2)\n",
    "            if tmp < numRows:\n",
    "                l = [None]*numRows\n",
    "                for j in range(i, min(i+numRows, len(s))):\n",
    "                    l[j-i] = s[j]\n",
    "                s1.append(l)\n",
    "                i += numRows\n",
    "                continue\n",
    "            else:\n",
    "                l = [None]*numRows\n",
    "                l[-(tmp - numRows + 2)] = s[i]\n",
    "                s1.append(l)\n",
    "            i += 1\n",
    "        s_out = \"\"\n",
    "        for j in range(numRows):\n",
    "            for i in range(len(s1)):\n",
    "                val = s1[i][j]\n",
    "                if not val:\n",
    "                    continue\n",
    "                s_out += val\n",
    "        return s_out\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        z_str = []\n",
    "        this_row = []\n",
    "        row_id = 0\n",
    "        blank = 0\n",
    "        if numRows == 1:\n",
    "            return s\n",
    "        for i in range(len(s)):\n",
    "            if blank == 0:\n",
    "                this_row.append(s[i])\n",
    "            else:\n",
    "                this_row = [\" \"] * (numRows - blank-1) + [s[i]] + [\" \"] * blank\n",
    "            if len(this_row) == numRows:\n",
    "\n",
    "                z_str.append(this_row)\n",
    "                row_id += 1\n",
    "                blank = row_id % (numRows - 1)\n",
    "                this_row = []\n",
    "        if len(this_row) > 0:\n",
    "            z_str.append(this_row + [\" \"] * (numRows - len(this_row)))\n",
    "        z_convert_str = \"\"\n",
    "        for k in range(numRows):\n",
    "            for j in range(len(z_str)):\n",
    "                if z_str[j][k] != \" \":\n",
    "                    z_convert_str += z_str[j][k]\n",
    "                else:\n",
    "                    continue\n",
    "        return z_convert_str\n",
    "                \n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        lens = len(s)\n",
    "        if numRows ==1:\n",
    "            return s\n",
    "        numcols = (lens//((numRows-1)*2))*(numRows-1) + (lens%((numRows-1)*2))//numRows + (lens%((numRows-1)*2))%numRows\n",
    "        arr = [[0 for _ in range(numcols)] for _ in range(numRows)]\n",
    "\n",
    "        c = 0\n",
    "        i = 0\n",
    "        j = 0\n",
    "        flag = True\n",
    "        while c < lens:\n",
    "            arr[i][j] = s[c]\n",
    "            c+=1\n",
    "            if flag:\n",
    "                i += 1\n",
    "                if i == numRows:\n",
    "                    i = numRows -2\n",
    "                    j += 1\n",
    "                    flag = False\n",
    "            else:\n",
    "                i -= 1\n",
    "                if i == -1:\n",
    "                    i = 1 \n",
    "                    flag = True\n",
    "                else:\n",
    "                    j += 1\n",
    "        news = ''\n",
    "        i = 0 \n",
    "        while i < numRows:\n",
    "            j = 0\n",
    "            while j < numcols:\n",
    "                if arr[i][j] != 0:\n",
    "                    news += arr[i][j]\n",
    "                j+=1\n",
    "            i+=1\n",
    "        return news    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "\n",
    "        if numRows==1:\n",
    "            return s \n",
    "        \n",
    "        def get_pos(idx, n=numRows):\n",
    "            idx += 1\n",
    "            m = 2*(n-1)\n",
    "            if idx % m == 0:\n",
    "                j = idx // 2\n",
    "                i = 1\n",
    "            else:\n",
    "                numZs = idx // m\n",
    "                j = numZs * (n-1)\n",
    "                if idx % m <= n:\n",
    "                    j += 1\n",
    "                    i = idx % m -1 \n",
    "                else:\n",
    "                    j += idx % m - n + 1\n",
    "                    i = 2*n - idx % m - 1\n",
    "            return i, j-1\n",
    "\n",
    "\n",
    "        numCols = get_pos(len(s)-1)[1] + 1\n",
    "\n",
    "        matrix = [[0 for i in range(numCols)] for j in range(numRows)]\n",
    "\n",
    "        for idx, ch in enumerate(s):\n",
    "            i, j = get_pos(idx)\n",
    "            matrix[i][j] = ch \n",
    "        \n",
    "        ans = \"\"\n",
    "        for i in range(numRows):\n",
    "            for j in range(numCols):\n",
    "                if matrix[i][j]:\n",
    "                    ans += matrix[i][j]\n",
    "        \n",
    "        return ans\n",
    "        \n",
    "            \n",
    "\n",
    "\n",
    "'''\n",
    "        if total % 2*(n-1) == 0:\n",
    "            numCols = total // 2\n",
    "        else:\n",
    "            numZs = total // 2*(n-1)\n",
    "            numCols = numZs * (n-1)\n",
    "            if total % 2*(n-1) <= n:\n",
    "                numCols += 1\n",
    "            else:\n",
    "                numCols += total % 2*(n-1) - n + 1  '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        if numRows == 1:\n",
    "            return s\n",
    "        oriLength = len(s)\n",
    "        singleZColumn = numRows - 1\n",
    "        singleZFullNum = numRows + singleZColumn - 1\n",
    "        ZNum = oriLength // singleZFullNum\n",
    "        modNum = oriLength - ZNum * singleZFullNum\n",
    "        modColumn = 0\n",
    "        if modNum > numRows:\n",
    "            modColumn = 1 + modNum - numRows\n",
    "        elif modNum > 0:\n",
    "            modColumn = 1\n",
    "        totalColumn = ZNum * singleZColumn + modColumn\n",
    "        matrix = ['' for _ in range(totalColumn * numRows)]\n",
    "        for index, char in enumerate(s):\n",
    "            ZIndex = index // singleZFullNum\n",
    "            ZStartStrIndex = ZIndex * singleZFullNum\n",
    "            ZEndStrIndex = ZIndex * singleZFullNum + singleZFullNum\n",
    "            offset = index - ZStartStrIndex\n",
    "            if offset - numRows < 0:\n",
    "                row = offset % numRows\n",
    "                column = ZIndex * singleZColumn\n",
    "            else:\n",
    "                row =  numRows - (offset - numRows )  - 2\n",
    "                column = ZIndex * singleZColumn + offset - numRows + 1\n",
    "            pos = totalColumn * row + column\n",
    "            matrix[pos] = char\n",
    "        result = \"\".join(matrix)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        L = []\n",
    "        L1 = []\n",
    "        L2 = []\n",
    "        res = ''\n",
    "        if len(s) <= numRows or numRows == 1:\n",
    "            return s\n",
    "        for i in range(len(s) // (numRows * 2 - 2) + 1):\n",
    "            L1.append(s[i * (numRows * 2 - 2):(i + 1) * (numRows * 2 - 2)])\n",
    "        for i in L1:\n",
    "            j = i[numRows:]\n",
    "            arr = ''\n",
    "            for _ in j:\n",
    "                arr += ' '*(numRows - 2) + _\n",
    "            i = i[:numRows] + arr + ' '*(numRows - 2)\n",
    "            L.append(i) \n",
    "        L[-1] += ((numRows*(numRows - 1) - (len(L[-1]))) * ' ' )\n",
    "        for i in L:\n",
    "            for j in range(len(i) // numRows):\n",
    "                L2.append(i[j * numRows:(j + 1)* numRows])\n",
    "\n",
    "        for i in range(numRows):\n",
    "            for j in L2:\n",
    "                res += j[i]\n",
    "        return res.replace(' ', '')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        if numRows == 1:\n",
    "            return s\n",
    "        k = math.ceil(len(s) / 2)\n",
    "        mat = [['#'] * k for _ in range(numRows)]\n",
    "\n",
    "        i = 0\n",
    "        m, n = 0, 0\n",
    "        direction = 1\n",
    "        for c in s:\n",
    "            mat[m][n] = c\n",
    "            m += direction\n",
    "            if direction == -1:\n",
    "                n += 1\n",
    "\n",
    "            if m == numRows:\n",
    "                m -= 2\n",
    "                n += 1\n",
    "                direction = -1\n",
    "            elif m == -1:\n",
    "                m += 2\n",
    "                n -= 1\n",
    "                direction = 1\n",
    "        \n",
    "        output = ''\n",
    "        for i in range(numRows):\n",
    "            for j in range(k):\n",
    "                if mat[i][j] != '#':\n",
    "                    output += mat[i][j]\n",
    "        return output\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        if numRows==1:\n",
    "            return s\n",
    "        else:\n",
    "            ans=''\n",
    "            n=len(s)\n",
    "            dp=[['0'for _ in range((n+1)//2)] for _ in range(numRows)]\n",
    "            for i,word in enumerate(s):\n",
    "                a=(i+1)%(2*numRows-2) #余数\n",
    "                b=(i+1)//(2*numRows-2)\n",
    "                if a==0:\n",
    "                    b=b-1\n",
    "                    a=2*numRows-2\n",
    "                if a<=numRows and a>0:\n",
    "                    dp[a-1][b*(numRows-1)]=word\n",
    "                else:\n",
    "                    dp[2*numRows-a-1][b*(numRows-1)+(a-numRows)]=word\n",
    "            for row in dp:\n",
    "                for element in row:\n",
    "                    if element!='0':\n",
    "                        ans+=element\n",
    "            return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        if len(s) <= numRows or numRows == 1:\n",
    "            return s\n",
    "        else:\n",
    "            # col numbers\n",
    "            N = len(s)\n",
    "            num_cols = 0\n",
    "            set_col = numRows*2-2\n",
    "            sets = N // set_col\n",
    "            rest = N % set_col\n",
    "            if rest <= numRows-1:\n",
    "                num_cols += 1\n",
    "            else:\n",
    "                num_cols = num_cols + rest%numRows + 1\n",
    "            num_cols = num_cols + sets*(numRows-1)\n",
    "            \n",
    "            mat = [[0]*num_cols for _ in range(numRows)]\n",
    "            \n",
    "            row,col,k = -1,0,0\n",
    "            for k in range(N):\n",
    "                if row < numRows-1 and col % (numRows-1) == 0:\n",
    "                    mat[row+1][col] = s[k]\n",
    "                    row += 1\n",
    "                else:\n",
    "                    mat[row-1][col+1] = s[k]\n",
    "                    row = row-1\n",
    "                    col = col+1\n",
    "            print(mat)\n",
    "            output = ''\n",
    "            for row in mat:\n",
    "                for ele in row:\n",
    "                    if ele != 0:\n",
    "                        output += ele\n",
    "            return output\n",
    "\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        resTmp = []\n",
    "        tmp = list(s)\n",
    "        if len(tmp) == 1:\n",
    "            resTmp.append(tmp)\n",
    "            return s\n",
    "        row = 0\n",
    "        # 先算z字变换，得到了z之后做个transpose\n",
    "        while True:\n",
    "            # 每个row填一次\n",
    "            if len(tmp) == 0:\n",
    "                break\n",
    "\n",
    "            rowLineTmp = [ \"#\" for _ in range(numRows)]\n",
    "            if numRows == 1:\n",
    "                resTmp = list(s)\n",
    "                break\n",
    "\n",
    "            if row%(numRows-1) == 0:\n",
    "                for i in range(numRows):\n",
    "                    rowLineTmp[i] = tmp.pop(0)\n",
    "                    if len(tmp) == 0:\n",
    "                        break\n",
    "            else:\n",
    "                rowLineTmp[-(row%(numRows-1))-1] = tmp.pop(0)\n",
    "\n",
    "            resTmp.append(rowLineTmp)\n",
    "            row += 1\n",
    "        \n",
    "        #遍历转置\n",
    "        resTmpTrans = [ [\"#\"]*len(resTmp) for _ in range(numRows)]\n",
    "        for i in range(len(resTmpTrans)):\n",
    "            for j in range(len(resTmpTrans[0])):\n",
    "                resTmpTrans[i][j] = resTmp[j][i]\n",
    "        \n",
    "        #遍历转字符串\n",
    "        res = \"\"\n",
    "        for line in resTmpTrans:\n",
    "            res += \"\".join(line)\n",
    "            \n",
    "        return res.replace(\"#\",\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        o = len(s)\n",
    "        if o <= numRows or len(s) <= 2 or numRows==1:\n",
    "            return s\n",
    "        if o<=3 and numRows==2:\n",
    "            return s[0]+s[2]+s[1]\n",
    "        if numRows ==2:\n",
    "            cache = \"\"\n",
    "            cache2 = \"\"\n",
    "            for i in range(o):\n",
    "                if i %2==0:\n",
    "                    cache += s[i]\n",
    "                else:\n",
    "                    cache2 += s[i]\n",
    "            return cache+cache2\n",
    "        result = []\n",
    "        for i in range(numRows):\n",
    "            result.append([])\n",
    "        full = True\n",
    "        out = []\n",
    "        i = 0\n",
    "        j = 0\n",
    "        k = 0\n",
    "        m = 0\n",
    "        n = 0\n",
    "        while j != len(s):\n",
    "            if k == numRows:\n",
    "                if not full:\n",
    "                    n -= 1\n",
    "                    m -= 1\n",
    "                else:\n",
    "                    if m == numRows - 2:\n",
    "                        m = 0\n",
    "                if m == 0:\n",
    "                    full = not full\n",
    "                    m = numRows - 2\n",
    "                if n == 0:\n",
    "                    n = numRows - 2\n",
    "\n",
    "                k = 0\n",
    "\n",
    "            if full:\n",
    "                result[i % numRows].append(s[j])\n",
    "                j += 1\n",
    "            else:\n",
    "                if k == n:\n",
    "                    result[i % numRows].append(s[j])\n",
    "                    j += 1\n",
    "                else:\n",
    "                    result[i % numRows].append(\"\")\n",
    "            k += 1\n",
    "            i += 1\n",
    "        for li in result:\n",
    "            out.extend(li)\n",
    "        return \"\".join(out)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        if numRows == 1 or len(s) <= numRows: return s\n",
    "        n, cols = len(s), 0\n",
    "        \n",
    "        while n > 0:\n",
    "            cols += 1\n",
    "            n = max(0, n - numRows)\n",
    " \n",
    "            if n >= numRows - 2:\n",
    "                n -= (numRows-2)\n",
    "                cols += (numRows-2)\n",
    "            elif n > 0:\n",
    "                cols += n\n",
    "                n = 0\n",
    "      \n",
    "        grid = [['0']*cols for _ in range(numRows)]\n",
    "        i, j, k = 0, 0, 0\n",
    "        print(cols)\n",
    "        while i < len(s):\n",
    "            while i < len(s) and k < numRows - 1:\n",
    "                grid[k][j] = s[i]\n",
    "                i += 1\n",
    "                k += 1\n",
    "    \n",
    "            while k > 0 and i < len(s) and j <= cols-1:\n",
    "                grid[k][j] = s[i]\n",
    "                i += 1\n",
    "                j += 1\n",
    "                k -= 1\n",
    "\n",
    "        return ''.join([grid[i][j] if grid[i][j]!='0' else '' for i in range(numRows) for j in range(cols)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        if numRows <= 1 or len(s) <= numRows:\n",
    "            return s\n",
    "        else:\n",
    "            letters_per_level = numRows + numRows - 2\n",
    "            rows_per_level = numRows - 1\n",
    "            a = int(len(s) / letters_per_level)\n",
    "            b = len(s) - a * letters_per_level\n",
    "            if b > numRows:\n",
    "                b = b - numRows + 1\n",
    "            else:\n",
    "                b = 1\n",
    "            numColumns = a * rows_per_level + b\n",
    "        matrix = []\n",
    "        for n in range(numRows):\n",
    "            line = [\"\"] * numColumns\n",
    "            matrix.append(line)\n",
    "        s = [c for c in s]\n",
    "        condition = 1\n",
    "        i,j = 1,0\n",
    "        matrix[0][0] = s.pop(0)\n",
    "        while len(s) > 0:\n",
    "            matrix[i][j] = s.pop(0)\n",
    "            if i >= numRows-1 or i <= 0:\n",
    "                condition *= -1\n",
    "            if condition == 1:\n",
    "                i += 1\n",
    "            else:\n",
    "                i -=1\n",
    "                j += 1\n",
    "        for i in range(numRows):\n",
    "            for j in range(numColumns):\n",
    "                    s.append(matrix[i][j])\n",
    "        return \"\".join(s)\n",
    "        # s = [c for c in s]\n",
    "        # while len(s)>0:\n",
    "        #     print(s.pop(0))\n",
    "        #     # print(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        if numRows <= 1 or len(s) <= numRows:\n",
    "            return s\n",
    "        else:\n",
    "            letters_per_level = numRows + numRows - 2\n",
    "            rows_per_level = numRows - 1\n",
    "            a = int(len(s) / letters_per_level)\n",
    "            b = len(s) - a * letters_per_level\n",
    "            if b > numRows:\n",
    "                b = b - numRows + 1\n",
    "            else:\n",
    "                b = 1\n",
    "            numColumns = a * rows_per_level + b\n",
    "        matrix = []\n",
    "        for n in range(numRows):\n",
    "            line = [\"\"] * numColumns\n",
    "            matrix.append(line)\n",
    "        s = [c for c in s]\n",
    "        condition = 1\n",
    "        i,j = 1,0\n",
    "        matrix[0][0] = s.pop(0)\n",
    "        while len(s) > 0:\n",
    "            matrix[i][j] = s.pop(0)\n",
    "            if i >= numRows-1 or i <= 0:\n",
    "                condition *= -1\n",
    "            if condition == 1:\n",
    "                i += 1\n",
    "            else:\n",
    "                i -=1\n",
    "                j += 1\n",
    "        for i in range(numRows):\n",
    "            for j in range(numColumns):\n",
    "                    s.append(matrix[i][j])\n",
    "        del matrix\n",
    "        return \"\".join(s)\n",
    "        # s = [c for c in s]\n",
    "        # while len(s)>0:\n",
    "        #     print(s.pop(0))\n",
    "        #     # print(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        if numRows == 1:\n",
    "            return s\n",
    "        array = [[None]*len(s) for _ in range(numRows)]\n",
    "        n, m = 0, 0\n",
    "        count  = 0\n",
    "        while count < len(s):\n",
    "            array[n][m] = s[count]\n",
    "            count += 1\n",
    "            if m%(numRows-1)==0 and n < numRows-1:\n",
    "                n+=1\n",
    "            elif n == numRows-1 or m%(numRows-1) != 0:\n",
    "                n -= 1\n",
    "                m += 1\n",
    "      #  print(array)\n",
    "        new_s = \"\"\n",
    "\n",
    "        for i in array:\n",
    "            for j in i:\n",
    "                if j:\n",
    "                    new_s += j\n",
    "      #  print(new_s)\n",
    "        return new_s\n",
    "        \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        n, r = len(s), numRows\n",
    "        if r == 1 or r >= n:\n",
    "            return s\n",
    "        t = r * 2 - 2\n",
    "        c = (n + t - 1) // t * (r - 1)\n",
    "        mat = [[''] * c for _ in range(r)]\n",
    "        x, y = 0, 0\n",
    "        for i, ch in enumerate(s):\n",
    "            mat[x][y] = ch\n",
    "            if i % t < r - 1:\n",
    "                x += 1  # 向下移动\n",
    "            else:\n",
    "                x -= 1\n",
    "                y += 1  # 向右上移动\n",
    "        return ''.join(ch for row in mat for ch in row if ch)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        n=len(s)\n",
    "        r=numRows\n",
    "        T=2*r-2\n",
    "        if r>=n or r==1:\n",
    "            return s\n",
    "        c=(n+T-1)//T*(r-1)\n",
    "        dp=[['']*c for _ in range(r)]\n",
    "        x,y=0,0\n",
    "        for i,ch in enumerate(s):\n",
    "            if i%T<r-1:\n",
    "                dp[x][y]=ch\n",
    "                x=x+1\n",
    "            else:\n",
    "                dp[x][y]=ch\n",
    "                x=x-1\n",
    "                y=y+1\n",
    "        return ''.join(ch for row in dp for ch in row if ch)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, s: str, numRows: int) -> str:\n",
    "        n = len(s)\n",
    "        if n <= numRows or numRows == 1:\n",
    "            return s\n",
    "        cloumn_cnt = (n//(2*numRows-2)+1)*(numRows-1)\n",
    "        res = [[\"-\"]*cloumn_cnt for _ in range(numRows)]\n",
    "        for i in range(n):\n",
    "            n_cnt = i//(2*numRows-2)\n",
    "            row_idx = i%(2*numRows-2)\n",
    "            cloumn_idx = 0\n",
    "            if row_idx >= numRows:\n",
    "                cloumn_idx += (row_idx + 1 - numRows)\n",
    "                row_idx = 2 * numRows - row_idx - 2\n",
    "            cloumn_idx += n_cnt * (numRows - 1)\n",
    "            res[row_idx][cloumn_idx] = s[i]\n",
    "        ret = \"\"\n",
    "        for i in range(numRows):\n",
    "            for j in range(cloumn_cnt):\n",
    "                if res[i][j] == \"-\":\n",
    "                    continue\n",
    "                ret += res[i][j]\n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
